package com.computer.fundamentals.algorithm;

/**
 * 数组小和 (剑指Offer 51.数组中的逆序对 改编)：
 *  ---------------------------------------------------------------------------
 *  在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
 *  例子：
 *  [1,3,4,2,5]
 *
 *  1左边比1小的数，没有；
 *  3左边比3小的数，1；
 *  4左边比4小的数，1、3；
 *  2左边比2小的数，1；
 *  5左边比5小的数，1、3、4、2；
 *
 *  所以小和为1+1+3+1+1+3+4+2=16
 *
 *  要求时间复杂度O(NlogN)，空间复杂度O(N)
 *  ---------------------------------------------------------------------------
 */
public class SmallSumArray {

    public int[] temp;
    public int sampleSum;

    /**
     * 解决方案
     *  利用归并排序，并的过程中发现分割的两个子组都是有序的
     *  如[1,3,4] 和 [2,5], 1小于2，那么1一定小于5，因此可以将1*2累加到结果中
     */
    public int solution(int[] nums) {
        temp = new int[nums.length];
        mergeSort(nums, 0, nums.length-1);
        return sampleSum;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        int i = left, j = mid+1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                sampleSum += nums[i] * (right - j + 1);
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        for (int m = 0;m < right - left + 1;m++) {
            nums[m + left] = temp[m];
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        SmallSumArray smallSumArray = new SmallSumArray();
        System.out.println("------------测试------------");
        System.out.println(smallSumArray.solution(new int[] {1,3,4,2,5}));

    }
}